package sortutil

import "math/rand"

func RandomQuickSort(arr []int) {
	if arr == nil || len(arr) < 2 {
		return
	}
	randomQuickSort(arr, 0, len(arr)-1)
}

func randomQuickSort(arr []int, start, end int) {
	if start < end {
		r := rand.Intn(end - start + 1)
		arr[start+r], arr[end] = arr[end], arr[start+r]
		p := partition(arr, start, end)
		randomQuickSort(arr, start, p[0])
		randomQuickSort(arr, p[1], end)
	}
}

func partition(arr []int, L, R int) [2]int {
	less, more := L-1, R
	for L < more {
		if arr[L] < arr[R] {
			less++
			arr[less], arr[L] = arr[L], arr[less]
			L++
		} else if arr[L] > arr[R] {
			more--
			arr[more], arr[L] = arr[L], arr[more]
		} else {
			L++
		}
	}
	arr[more], arr[R] = arr[R], arr[more]
	return [2]int{less, more + 1}
}
